package com.leetcode.LeetCode精选TOP面试题;

import com.leetcode.common.model.TreeNode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-06-07 18:22
 */
public class 题库_0094_二叉树的中序遍历 {

  static
  class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> answers = new ArrayList<>();
//      inorderTraversalWithBacktrack(answers, root);
      inorderTraversalWithStack(answers, root);
      return answers;
    }

    private void inorderTraversalWithStack(List<Integer> answers, TreeNode root) {
      if (root == null) {
        return;
      }

      Deque<TreeNode> stack = new ArrayDeque<>();

      while (!stack.isEmpty() || root != null) {
        if (root != null) {
          stack.push(root);
          root = root.left;
        } else {
          root = stack.pop();
          answers.add(root.val);
          root = root.right;
        }
      }
    }

    private void inorderTraversalWithBacktrack(List<Integer> answers, TreeNode root) {
      if (root == null) {
        return;
      }
      inorderTraversalWithBacktrack(answers, root.left);
      answers.add(root.val);
      inorderTraversalWithBacktrack(answers, root.right);
    }

  }

}
